# 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
# 并将P对1000000007取模的结果输出。 即输出P%1000000007
# 他的意思是，只要有前面的数字大于后面的，那就算数，不是说两个数非得紧挨着
# [1,2,3,0],这里面有3对逆序数


# 这个方法属于暴力求解，可以运行，但是牛客网上超时，需要用归并法
def InversePairs(data):
    res = 0
    for i in range(len(data)):
        temp = data[i+1:]
        for j in temp:
            if data[i]>j:
                res+=1
    return res%1000000007

# 解法2,很不错的想法，可惜还是超时，估计是数组查找，数组remove并且重排还是费时间
def InversePairs1(data):
    res = data[:]
    count = 0
    res.sort()

    for i in range(len(count)):
        count+=data.index(res[i])
        data.remove(res[i])

    return count%1000000007
# 解法3，剑指offer笔记解法，依然无法通过，停在75%
class Solution:
    def InversePairs(self, data):
        # write code here
        if not data:
            return 0
        temp = [i for i in data]
        return self.mergeSort(temp, data, 0, len(data) - 1) % 1000000007

    def mergeSort(self, temp, data, low, high):
        if low >= high:
            temp[low] = data[low]
            return 0
        mid = (low + high) / 2
        left = self.mergeSort(data, temp, low, mid)
        right = self.mergeSort(data, temp, mid + 1, high)

        count = 0
        i = low
        j = mid + 1
        index = low
        while i <= mid and j <= high:
            if data[i] <= data[j]:
                temp[index] = data[i]
                i += 1
            else:
                temp[index] = data[j]
                count += mid - i + 1
                j += 1
            index += 1
        while i <= mid:
            temp[index] = data[i]
            i += 1
            index += 1
        while j <= high:
            temp[index] = data[j]
            j += 1
            index += 1
        return count + left + right


# print(InversePairs([1,2,3,4,5,6,7,0]))
res1 = [1,2,3,0]
res = res1[:]
res.sort()
print(res1)